#include<bits/stdc++.h>
#define int long long
#define ls(x) ((x)*2)
#define rs(x) ((x)*2+1)
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i,  b) for(int i=1,i##end=b;i<=i##end;i++)
using namespace std;
const int N=1e6+5,base=999983,Mod=998244353;
//char buf[(1<<21)+5],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline void chmx(int &x,int y){(x<y)&&(x=y);}
inline void chmn(int &x,int y){(x>y)&&(x=y);}
inline void Add(int &x,int y){(x=x+y+Mod)%=Mod;}
inline int read(){
	int f=0,x=0;
	char ch=getchar();
	while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f?-x:x;
}
void print(int n){
    if(n<0){
        putchar('-');
        n*=-1;
    }
    if(n>9) print(n/10);
    putchar(n%10+'0');
}
int a[N];
set<int>s;
int qzh[N],hzh[N];
map<int,int>mp;
int answer[N],c[N];
int gg[N],tot;
signed main(){
	freopen("kte.in","r",stdin);
	freopen("kte.out","w",stdout);
	// ios::sync_with_stdio(false);
	// cin.tie(0); cout.tie(0);
	int T=read();int n=0;
	if(T<=400000){
		while(T--){
			int x=read();mp[x]^=1;
			int lim=1;
			int p=0;
			if(!mp[x]){
				p=0;
				For(i,1,n){
					if(a[i]==x){
						p=i;break;
					}
				}n--;For(i,p,n) a[i]=a[i+1];
				lim=min(p-1,n-p+1);
			}else{
				p=n+1;
				For(i,1,n){
					if(a[i]>x){
						p=i;break;
					}
				}
				Rof(i,n,p) a[i+1]=a[i];
				a[p]=x;
				n++;
				lim=min(p-1,n-p);
			}
			if(n<=1){
				puts("0");
				continue;
			}
			lim++;
			int l=lim,r=n-lim+1;
			int mn=qzh[lim-1],mx=hzh[lim-1];
			int ans=answer[lim-1],lst=hzh[lim-1];
			For(i,lim,n-1){
				mn+=a[l],mx+=a[r];
				lst=max(lst,mn);
				ans+=max(0ll,mx-lst);
				qzh[i]=mn,hzh[i]=mx,answer[i]=ans;
				lst=mx;
				if(i!=n) l++,r--;
			}
			printf("%lld\n",ans);
		}
		return 0;
	}
#ifdef LOCAL
    Debug("\nMy Time: %.3lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}

